package com.algorithm.MultipleFactory;

import java.util.*;

public class MultipleFactory {
    private static int m;  // 机器数
    private static int n;  // 工件数
    private static Job[] jobs;  // 工件

    private static int sumLastMachineTime = 0;

    public static void main(String[] args) {
        initProblem();
        printJobs();
        PriorityQueue<Node> queue = getPriorityQueue();  // 创建优先队列
        sumLastMachineTime = getSumLastMachineTime();  // 计算所有工件在最后一个机器的加工的总时间
        Node root = getRootNode();
        int bestTime = 100000000;
        Node resultNode = null;
        queue.add(root);
        while (!queue.isEmpty()) {
            Node fatherNode = queue.poll();  // 取出队首元素
            // 如果这个节点没前途
            if (fatherNode.prospect >= bestTime) {
                continue;
            }
            // 如果这个节点是最后一个节点，则不进行拓展
            if (fatherNode.count == n) {
                if (fatherNode.costTime < bestTime) {
                    bestTime = fatherNode.costTime;
                    resultNode = fatherNode;
                    // 如果前途指数和现实指数一样，那么说明找到了最优解。
                    if (fatherNode.costTime == fatherNode.prospect) {
                        break;
                    }
                }
                continue;
            }
            // 对队首节点进行拓展
            // 去除已经做过的工件
            List<Integer> help = getHelpArray();
            for (Node node = fatherNode; node.jobIndex != -1; node = node.father) {
                help.set(node.jobIndex, -1);
            }
            for (int i = n - 1; i >= 0; --i) {
                if (help.get(i) == -1) {
                    help.remove(i);
                }
            }
            // 扩展
            for (int i = 0; i < help.size(); ++i) {
                Node son = new Node();
                son.jobIndex = help.get(i);
                son.father = fatherNode;
                son.count = fatherNode.count + 1;
                son.beginTime[0] = fatherNode.beginTime[1];
                for (int k = 1; k < m - 1; ++k) {
                    son.beginTime[k] = Math.max(fatherNode.beginTime[k + 1], son.beginTime[k - 1] + jobs[son.jobIndex].machine[k - 1]);
                }
                if (fatherNode.jobIndex == -1) {
                    son.beginTime[m - 1] = son.beginTime[m - 2] + jobs[son.jobIndex].machine[m - 2];
                } else {
                    son.beginTime[m - 1] = Math.max(fatherNode.beginTime[m - 1] + jobs[fatherNode.jobIndex].machine[m - 1], son.beginTime[m - 2] + jobs[son.jobIndex].machine[m - 2]);
                }
                son.costTime = son.beginTime[m - 1] + jobs[son.jobIndex].machine[m - 1];
                int sum = 0;
                for (int k = 0; k < help.size(); ++k) {
                    sum += jobs[help.get(k)].machine[m - 1];
                }
                son.prospect = son.beginTime[m - 1] + sum;
                if (son.prospect > bestTime) {
                    continue;
                }
                queue.add(son);
            }


        }
        Stack<Integer> stack = new Stack<>();
        for (Node node = resultNode; node.jobIndex != -1; node = node.father) {
            stack.push(node.jobIndex);
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.print(bestTime);
    }

    private static void initProblem() {
        System.out.println("请输入机器数和工件数");
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        n = scanner.nextInt();
        Job.m = Node.m = m;
        jobs = new Job[n];
        System.out.println("请输入每个工件在各个机器上的耗时");
        for (int i = 0; i < n; ++i) {
            jobs[i] = new Job();
            for (int j = 0; j < m; ++j) {
                jobs[i].machine[j] = scanner.nextInt();
            }
        }
    }

    private static void printJobs() {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                System.out.print(jobs[i].machine[j] + " ");
            }
            System.out.println();
        }
    }

    private static PriorityQueue<Node> getPriorityQueue() {
        Comparator<Node> cmp = new Comparator<Node>() {
            @Override
            public int compare(Node node, Node t1) {
                return node.prospect - t1.prospect;   //从小到大进行排列
            }
        };
        return new PriorityQueue<>(cmp);
    }

    private static int getSumLastMachineTime() {
        int sumLastMachineTime = 0;
        for (int i = 0; i < n; ++i) {
            sumLastMachineTime += jobs[i].machine[m - 1];
        }
        return sumLastMachineTime;
    }

    private static Node getRootNode() {
        Node root = new Node();
        root.jobIndex = -1;
        for (int i = 0; i < m; ++i) {
            root.beginTime[i] = 0;
        }
        root.costTime = 0;
        root.count = 0;
        root.father = null;
        root.prospect = sumLastMachineTime;
        return root;
    }

    private static List<Integer> getHelpArray() {
        List<Integer> help = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            help.add(i);
        }
        return help;
    }
}
